package com.learn.tree;

/**
 * 前缀树
 */
public class TriedTree {
    public static class Node {
        private int pass;
        private int end;
        private Node[] nexts;

        public Node() {
            pass = 0;
            end = 0;
            //只构建a-z的前缀树
            nexts = new Node[26];
        }
    }

    public static class Tree {
        private Node root;

        public Tree(){
            root = new Node();
        }

        public void insert(String value) {
            if (value == null) {
                return;
            }
            Node node = root;
            node.pass++;
            char[] str = value.toCharArray();
            for (int i = 0; i < str.length; i++) {
                int index = str[i] - 'a';
                if (node.nexts[index] == null) {
                    node.nexts[index] = new Node();
                }
                node = node.nexts[index];
                node.pass++;

            }
            root.end++;

        }

        /**
         * 查看一个单词是否出现过
         *
         * @param word
         * @return
         */
        public int search(String word) {
            if (word == null) {
                return 0;
            }
            Node node = root;
            char[] chars = word.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                int index = chars[i] - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.end;
        }

        /**
         * 查找前缀出现的次数
         *
         * @param pre
         * @return
         */
        public int findPreFixNum(String pre) {
            if (pre == null) {
                return 0;
            }

            Node node = root;

            char[] chars = pre.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                int index = chars[i] - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.pass;
        }


        public void delete(String word) {
            if (word == null) {
                return;
            }
            if(search(word)!=0){
                Node node = root;
                node.pass--;
                char[] chars = word.toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    int index = chars[i] - 'a';
                    if (--node.nexts[index].pass == 0) {
                        node.nexts[index] = null;
                        return;
                    }
                    node = node.nexts[index];
                }
                node.end--;
            }

        }
    }
}
